import java.util.ArrayList;
import java.util.List;

public class Solution2081 {
    private static final long[][] TABLES = {
            // 2
            {1, 3, 5, 7, 9, 33, 99, 313, 585, 717, 7447, 9009, 15351, 32223, 39993, 53235, 53835, 73737, 585585, 1758571, 1934391, 1979791, 3129213, 5071705, 5259525, 5841485, 13500531, 719848917, 910373019, 939474939},
            // 3
            {1, 2, 4, 8, 121, 151, 212, 242, 484, 656, 757, 29092, 48884, 74647, 75457, 76267, 92929, 93739, 848848, 1521251, 2985892, 4022204, 4219124, 4251524, 4287824, 5737375, 7875787, 7949497, 27711772, 83155138},
            // 4
            {1, 2, 3, 5, 55, 373, 393, 666, 787, 939, 7997, 53235, 55255, 55655, 57675, 506605, 1801081, 2215122, 3826283, 3866683, 5051505, 5226225, 5259525, 5297925, 5614165, 5679765, 53822835, 623010326, 954656459, 51717171715L},
            // 5
            {1, 2, 3, 4, 6, 88, 252, 282, 626, 676, 1221, 15751, 18881, 10088001, 10400401, 27711772, 30322303, 47633674, 65977956, 808656808, 831333138, 831868138, 836131638, 836181638, 2512882152L, 2596886952L, 2893553982L, 6761551676L, 12114741121L, 12185058121L},
            // 6
            {1, 2, 3, 4, 5, 7, 55, 111, 141, 191, 343, 434, 777, 868, 1441, 7667, 7777, 22022, 39893, 74647, 168861, 808808, 909909, 1867681, 3097903, 4232324, 4265624, 4298924, 4516154, 4565654},
            // 7
            {1, 2, 3, 4, 5, 6, 8, 121, 171, 242, 292, 16561, 65656, 2137312, 4602064, 6597956, 6958596, 9470749, 61255216, 230474032, 466828664, 485494584, 638828836, 657494756, 858474858, 25699499652L, 40130703104L, 45862226854L, 61454945416L, 64454545446L},
            // 8
            {1, 2, 3, 4, 5, 6, 7, 9, 121, 292, 333, 373, 414, 585, 3663, 8778, 13131, 13331, 26462, 26662, 30103, 30303, 207702, 628826, 660066, 1496941, 1935391, 1970791, 4198914, 55366355},
            // 9
            {1, 2, 3, 4, 5, 6, 7, 8, 191, 282, 373, 464, 555, 646, 656, 6886, 25752, 27472, 42324, 50605, 626626, 1540451, 1713171, 1721271, 1828281, 1877781, 1885881, 2401042, 2434342, 2442442}
    };

    public long kMirror(int k, int n) {
        long[] table = TABLES[k - 2];
        long ans = 0;
        for (int i = 0; i < n; i++) {
            ans += table[i];
        }
        return ans;
    }

    // 打表
    public static void main(String[] args) {
        // -Xms16G -Xmx16G
        double totalMemory = Runtime.getRuntime().totalMemory();
        double maxMemory = Runtime.getRuntime().maxMemory();
        System.out.println("totalMemory: " + totalMemory / (double) 1024 / 2024 + "MB");
        System.out.println("maxMemory: " + maxMemory / (double) 1024 / 2024 + "MB");
        print();
    }

    static void print() {
        List<Long> pal = new ArrayList<>();
        for (int L = 1; L <= 6; L++) {
            int low = (int) Math.pow(10, L - 1);
            int high = (int) Math.pow(10, L);
            // Check for odd-length palindromes
            for (int root = low; root < high; root++) {
                long p = root;
                for (int x = root / 10; x > 0; x /= 10) {
                    p = p * 10 + x % 10;
                }
                pal.add(p);
            }
            // Check for even-length palindromes
            for (int root = low; root < high; root++) {
                long p = root;
                for (int x = root; x > 0; x /= 10) {
                    p = p * 10 + x % 10;
                }
                pal.add(p);
            }
        }

        for (int k = 2; k <= 9; k++) {
            int id = 1;
            System.out.println(k + " 进制");
            for (Long base10 : pal) {
                String baseK = Long.toString(base10, k);
                if (isPal(baseK)) {
                    System.out.println(id++ + ":" + base10 + ":" + baseK);
                    if (id > 30) break;
                }
            }
            System.out.println();
        }
    }

    private static boolean isPal(String s) {
        return new StringBuilder(s).reverse().toString().equals(s);
    }
}
/*
2081. k 镜像数字的和
https://leetcode.cn/problems/sum-of-k-mirror-numbers/

第 268 场周赛 T4。

一个 k 镜像数字 指的是一个在十进制和 k 进制下从前往后读和从后往前读都一样的 没有前导 0 的 正 整数。
比方说，9 是一个 2 镜像数字。9 在十进制下为 9 ，二进制下为 1001 ，两者从前往后读和从后往前读都一样。
相反地，4 不是一个 2 镜像数字。4 在二进制下为 100 ，从前往后和从后往前读不相同。
给你进制 k 和一个数字 n ，请你返回 k 镜像数字中 最小 的 n 个数 之和 。
提示：
2 <= k <= 9
1 <= n <= 30

答案范围很少，考虑打表。一开始逐个数加 1 去枚举，结果到比赛结束也没把表打完。。
本题 7 进制需要枚举到 64454545446，考虑先枚举每个 10 进制回文数，再判断对应 k 进制数是否满足回文。

long 64bit 8Byte
1-2位 10
3-4位 100
5-6位 1000
7-8位 10000
9-10位 100000
11-12位 1000000
13-14位 10000000
15-16位 100000000

totalMemory: 8289.138339920948MB
maxMemory: 8289.138339920948MB
2 进制
1:1:1
2:3:11
3:5:101
4:7:111
5:9:1001
6:33:100001
7:99:1100011
8:313:100111001
9:585:1001001001
10:717:1011001101
11:7447:1110100010111
12:9009:10001100110001
13:15351:11101111110111
14:32223:111110111011111
15:39993:1001110000111001
16:53235:1100111111110011
17:53835:1101001001001011
18:73737:10010000000001001
19:585585:10001110111101110001
20:1758571:110101101010101101011
21:1934391:111011000010000110111
22:1979791:111100011010110001111
23:3129213:1011111011111101111101
24:5071705:10011010110001101011001
25:5259525:10100000100000100000101
26:5841485:10110010010001001001101
27:13500531:110011100000000001110011
28:719848917:101010111010000000010111010101
29:910373019:110110010000110011000010011011
30:939474939:110111111111110011111111111011
31:1290880921:1001100111100010100011110011001
32:7451111547:110111100000111101111000001111011
33:10050905001:1001010111000101001010001110101001
34:18462126481:10001001100011011011011000110010001
35:32479297423:11110001111111010101011111110001111
36:75015151057:1000101110111010000000101110111010001
37:110948849011:1100111010101000100010001010101110011
38:136525525631:1111111001001100011100011001001111111
39:1234104014321:10001111101010110010101001101010111110001
40:1413899983141:10100100100110011000000011001100100100101
41:1474922294741:10101011101101000001110000010110111010101
42:1792704072971:11010000101100101011111010100110100001011
43:1794096904971:11010000110111000100000100011101100001011
44:1999925299991:11101000110100100110101100100101100010111
45:5652622262565:1010010010000011010100010101100000100100101
46:7227526257227:1101001001011001010001000101001101001001011
47:7284717174827:1101010000000011010111110101100000000101011
48:9484874784849:10001010000001011110100101111010000001010001
49:34141388314143:111110000110100101001010100101001011000011111
50:552212535212255:1111101100011110000000000000000000111100011011111

3 进制
1:1:1
2:2:2
3:4:11
4:8:22
5:121:11111
6:151:12121
7:212:21212
8:242:22222
9:484:122221
10:656:220022
11:757:1001001
12:29092:1110220111
13:48884:2111001112
14:74647:10210101201
15:75457:10211111201
16:76267:10212121201
17:92929:11201110211
18:93739:11202120211
19:848848:1121010101211
20:1521251:2212021202122
21:2985892:12121200212121
22:4022204:21120100102112
23:4219124:21221100112212
24:4251524:21222222222212
25:4287824:22001211210022
26:5737375:101210111012101
27:7875787:112211010112211
28:7949497:112221212122211
29:27711772:1221010220101221
30:83155138:12210110201101221
31:112969211:21212120102121212
32:123464321:22121022122012122
33:211131112:112201021120102211
34:239060932:121122211112221121
35:387505783:1000000011100000001
36:520080025:1100020121210200011
37:885626588:2021201110111021202
38:2518338152:20111111200211111102
39:58049094085:12112211112121111221121
40:81234543218:21202200101010100220212
41:2121010101212:21111202200211200220211112
42:4320048400234:120021222210121012222120021
43:4657098907564:121111012210020012210111121
44:4978471748794:122121221022020220122121221
45:5972209022795:210010221022111220122010012
46:6852190912586:220021001200222002100120022
47:69490044009496:100010001011221122110100010001
48:438222212222834:2010110121122010102211210110102
49:534174353471435:2121001100120101010210011001212
50:1984267447624891:100122012201010010010102210221001

4 进制
1:1:1
2:2:2
3:3:3
4:5:11
5:55:313
6:373:11311
7:393:12021
8:666:22122
9:787:30103
10:939:32223
11:7997:1330331
12:53235:30333303
13:55255:31133113
14:55655:31211213
15:57675:32011023
16:506605:1323223231
17:1801081:12313231321
18:2215122:20130303102
19:3826283:32212021223
20:3866683:32300000323
21:5051505:103101101301
22:5226225:103323323301
23:5259525:110010010011
24:5297925:110031130011
25:5614165:111122221111
26:5679765:111222222111
27:53822835:3031110111303
28:623010326:211020212020112
29:954656459:320321232123023
30:51717171715:300022211112220003
31:53406060435:301233033330332103
32:59201610295:313020230032020313
33:73979697937:1010321202021230101
34:506802208605:13113333300333331131
35:508152251805:13121100033000112131
36:1491278721941:111230313020313032111
37:1649061609461:113333303232303333311
38:3445416145443:302020302303203020203
39:5690277720965:1102303132332313032011
40:41830077003814:21200231102320113200212
41:646219242912646:2102323232210122323232012
42:815969141969518:2321201322132312231021232
43:912702454207219:3033201210121210121023303
44:7145572222755417:121120231300232003132021121

5 进制
1:1:1
2:2:2
3:3:3
4:4:4
5:6:11
6:88:323
7:252:2002
8:282:2112
9:626:10001
10:676:10201
11:1221:14341
12:15751:1001001
13:18881:1101011
14:10088001:10040304001
15:10400401:10130303101
16:27711772:24043234042
17:30322303:30230303203
18:47633674:44143234144
19:65977956:113342243311
20:808656808:3124004004213
21:831333138:3200310130023
22:831868138:3200424240023
23:836131638:3203022203023
24:836181638:3203030303023
25:2512882152:20121244212102
26:2596886952:20304300340302
27:2893553982:21411222211412
28:6761551676:102321424123201
29:12114741121:144302333203441
30:12185058121:144423333324441
31:2228261628222:243001434434100342
32:6105769675016:1300014104014100031
33:6643369633466:1332321110111232331
34:6648130318466:1332410332330142331
35:6694978794966:1334142304032414331
36:6982578752896:1403400310130043041
37:6989062609896:1404002100012004041
38:7730173710377:2003122343432213002
39:103191131191301:102011140414041110201
40:103824717428301:102102031010130201201
41:107745787547701:103110301333103011301
42:107793080397701:103112040212040211301
43:132412434214231:114323421131124323411
44:172102080201271:140024210030012420041
45:172849181948271:140123430111034321041
46:176071838170671:141034230111032430141
47:176265757562671:141100414232414001141
48:202304515403202:203004024121420400302
49:206725444527602:204043442202244340402
50:206903565309602:204104402000204401402

6 进制
1:1:1
2:2:2
3:3:3
4:4:4
5:5:5
6:7:11
7:55:131
8:111:303
9:141:353
10:191:515
11:343:1331
12:434:2002
13:777:3333
14:868:4004
15:1441:10401
16:7667:55255
17:7777:100001
18:22022:245542
19:39893:504405
20:74647:1333331
21:168861:3341433
22:808808:25200252
23:909909:31300313
24:1867681:104010401
25:3097903:150222051
26:4232324:230414032
27:4265624:231232132
28:4298924:232050232
29:4516154:240444042
30:4565654:241505142
31:4598954:242323242
32:4849484:251535152
33:5100015:301151103
34:5182815:303030303
35:5400045:311424113
36:5433345:312242213
37:5482845:313303313
38:5733375:322515223
39:5766675:323333323
40:5799975:324151423
41:6901096:403525304
42:6934396:404343404
43:6983896:405404504
44:8164618:450555054
45:9081809:522353225
46:15266251:1303113031
47:24466442:2232222322
48:103656301:14141414141
49:104888401:14224042241
50:108151801:14422022441

7 进制
1:1:1
2:2:2
3:3:3
4:4:4
5:5:5
6:6:6
7:8:11
8:121:232
9:171:333
10:242:464
11:292:565
12:16561:66166
13:65656:362263
14:2137312:24111142
15:4602064:54055045
16:6597956:110040011
17:6958596:113101311
18:9470749:143333341
19:61255216:1342442431
20:230474032:5465665645
21:466828664:14365656341
22:485494584:15013431051
23:638828836:21554645512
24:657494756:22202420222
25:858474858:30162626103
26:25699499652:1566600066651
27:40130703104:2620322230262
28:45862226854:3212336332123
29:61454945416:4303624263034
30:64454545446:4441146411444
31:65796069756:4516326236154
32:75016161057:5263653563625
33:75431213457:5310153510135
34:90750705709:6361613161636
35:91023932019:6401441441046
36:95365056359:6614143414166
37:426970079624:42563500536524
38:775350053577:110005616500011
39:1269880889621:160513555315061
40:2264092904622:322401222104223
41:2451956591542:342101525101243
42:2680120210862:364426606624463
43:2745382835472:402230101032204
44:2928299928292:421364000463124
45:4158563658514:606306040603606
46:6750989890576:1264512552154621
47:8868067608688:1603460660643061
48:23419766791432:4635010440105364
49:49929477492994:13342166666124331
50:74194966949147:21425260306252412

8 进制
1:1:1
2:2:2
3:3:3
4:4:4
5:5:5
6:6:6
7:7:7
8:9:11
9:121:171
10:292:444
11:333:515
12:373:565
13:414:636
14:585:1111
15:3663:7117
16:8778:21112
17:13131:31513
18:13331:32023
19:26462:63536
20:26662:64046
21:30103:72627
22:30303:73137
23:207702:625526
24:628826:2314132
25:660066:2411142
26:1496941:5553555
27:1935391:7304037
28:1970791:7411147
29:4198914:20011002
30:55366355:323151323
31:130535031:761747167
32:532898235:3760660673
33:719848917:5272002725
34:799535997:5751771575
35:1820330281:15440004451
36:2464554642:22271417222
37:4424994244:40760006704
38:4480880844:41305150314
39:4637337364:42432023424
40:20855555802:233305503332
41:94029892049:1274447444721
42:94466666449:1277651567721
43:294378873492:4221226221224
44:390894498093:5540310130455
45:5227529257225:114044101440411
46:5853143413585:125131242131521
47:7712150512177:160163777361061
48:13994688649931:313514434415313
49:28719555591782:641731272137146
50:34926999962943:774202333202477

9 进制
1:1:1
2:2:2
3:3:3
4:4:4
5:5:5
6:6:6
7:7:7
8:8:8
9:191:232
10:282:343
11:373:454
12:464:565
13:555:676
14:646:787
15:656:808
16:6886:10401
17:25752:38283
18:27472:41614
19:42324:64046
20:50605:76367
21:626626:1154511
22:1540451:2807082
23:1713171:3201023
24:1721271:3213123
25:1828281:3385833
26:1877781:3471743
27:1885881:3483843
28:2401042:4458544
29:2434342:4520254
30:2442442:4532354
31:2450542:4544454
32:3106013:5753575
33:3114113:5765675
34:3122213:5777775
35:3163613:5851585
36:3171713:5863685
37:3303033:6183816
38:3360633:6281826
39:65666656:146505641
40:167191761:378535873
41:181434181:418353814
42:232000232:534484435
43:382000283:877717778
44:5435665345:15024142051
45:8901111098:24870007842
46:9565335659:26617771662
47:827362263728:2832508052382
48:1400232320041:4855217125584
49:2005542455002:7081580851807
50:2024099904202:7144500054417
 */